//
// Created by ASUS on 2024/1/29.
//
#include <bits/stdc++.h>
using namespace std;

vector<int> preSum(vector<int>&a){
	int n=a.size();
	vector<int> s(n+1,0);
	for(int i=0;i<n;i++){
		s[i+1]=s[i]+a[i];
	}
	return s;//a[l:r]=s[r+1]-s[l];
}
vector<vector<int>> preSum2D(vector<vector<int>>&a){
	int m=a.size(),n=a[0].size();
	vector<vector<int>> s(m+1,vector<int>(n+1,0));
	for(int i=0;i<m;i++){
		for(int j=0;j<n;j++){
			s[i+1][j+1]=s[i][j+1]+s[i+1][j]-s[i][j]+a[i][j];
		}
	}
	return s;//a[l1:r1][l2:r2]=s[r1+1][r2+1]-s[r1+1][l2]-s[l1][r2+1]+s[l1][l2];
}


int main(){

	vector<int> a{1,3,7,9,13,2,-5};
	vector<int> b= preSum(a);
	cout<<b[3+1]-b[0]<<endl;

	vector<vector<int>> c={{1,3,4},{3,7,1},{6,6,6},{21,99,0}};
	auto d= preSum2D(c);
	int x1=1,x2=2,y1=1,y2=2;
	cout<<d[x2+1][y2+1]-d[x1][y2+1]-d[x2+1][y1]+d[x1][y1]<<endl;
	return 0;
}
